1. Insertion Sort¶

Insertion-sort-example.gif

In [9]:
def insertion(my_list):
    for i in range(1,len(my_list)):
        k = i
        while i>0 and my_list[i] < my_list[i-1]:
            my_list[i],my_list[i-1]=my_list[i-1],my_list[i]
            i=i-1
        print(my_list)
    print('sorted',my_list)    
list1=[4,6,3,9,2]
print('Unsorted',list1)
insertion(list1)
Unsorted [4, 6, 3, 9, 2]
[4, 6, 3, 9, 2]
[3, 4, 6, 9, 2]
[3, 4, 6, 9, 2]
[2, 3, 4, 6, 9]
sorted [2, 3, 4, 6, 9]

2. Selection Sort¶

selection.gif

In [24]:
def selection(my_list):
    for i in range(0,len(my_list)-1):
        for j in range(i+1,len(my_list)):
            if my_list[i] > my_list[j]:
                my_list[i],my_list[j]=my_list[j],my_list[i]
            
    print('sorted:',my_list)
        
list1=[6,8,3,5,9,10,7,2,4,1]
print('unsorted',list1)
selection(list1)
unsorted [6, 8, 3, 5, 9, 10, 7, 2, 4, 1]
sorted: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

3. Bubble sort</b></h1>¶

bubble_sort_ani.gif

In [30]:
def bubble(my_list):
    for i in range(0,len(my_list)):
        
        for j in range(0,len(my_list)-1):
            
            if my_list[j] > my_list[j+1]:
                
                my_list[j],my_list[j+1]= my_list[j+1],my_list[j]
                
    print('sorted:',my_list)

list2=[7,8,2,0,1]
print('unsorted:',list2)
bubble(list2)
unsorted: [7, 8, 2, 0, 1]
sorted: [0, 1, 2, 7, 8]

4. Merge sort¶

merge3.gif

In [5]:
def mergesort(list1):
    if len(list1)>1:
        mid = len(list1)//2
        
        left_list = list1[:mid]
        right_list = list1[mid:]
        
        mergesort(left_list)
        mergesort(right_list)
        
        i=0
        j=0
        k=0
        
        while i<len(left_list) and j<len(right_list):
            if left_list[i] < right_list[j]:
                list1[k] = left_list[i]
                i=i+1
                k=k+1
                
            else:
                list1[k] = right_list[j]
                j=j+1
                k=k+1
                
            
                
        while i<len(left_list):
            list1[k]=left_list[i]
            i=i+1
            k=k+1
            
        while j<len(right_list):
            list1[k] = right_list[j]
            j=j+1
            k=k+1
            
list2=[7,8,2,0,1]
print('unsorted:',list2)
mergesort(list2)
print('sorted list',list2)            
unsorted: [7, 8, 2, 0, 1]
sorted list [0, 1, 2, 7, 8]

5. Quick sort¶

quick_sort_partition_animation.gif

In [1]:
# Easy way but not efficient way

def quick(list1):
    if len(list1) <= 1:
        return list1
    else:
        pivot=list1.pop()
        
    greater=[]
    lesser=[]
        
    for i in list1:
        if i > pivot:
            greater.append(i)
                
        else:
            lesser.append(i)
                
    return quick(lesser)+[pivot]+quick(greater)
    
li=[54,5,6,2,1,97,3]
print(quick(li))
[1, 2, 3, 5, 6, 54, 97]
In [33]:
#efficitent method
#"""three condition must be for quick sort"""
# 1] left <= right
# 2] left <= pivot if true then next left , if flase then stop and control goes to right side
# 3] right >= pivot if true the next right , if flase then stop and control goes for swapping

def pivot_place(list1,first,last):
    pivot=list1[first]
    
    left=first+1
    right=last
    
    while True:
        while left <= right and list1[left] <= pivot :
            left=left+1
        while left <= right and list1[right] >= pivot:
            right= right-1
            
        if right < left :
            break
        else:
            list1[left],list1[right]=list1[right],list1[left]
            
    list1[first],list1[right]=list1[right],list1[first]
    #print("1:",id(list1))
    return right

def quicksort(list1,first,last):
    if first < last:
        p = pivot_place(list1,first,last)
        print(list1)
        #print("2:",id(list1))
        #print(p)
        quicksort(list1,first,p-1)
        quicksort(list1,p+1,last)
        
        
     
    
    
li=[54,5,6,2,1,97,3]
n=len(li)
quicksort(li,0,n-1)
print("sorted List = ",li)
print("memory loc 3:",id(li))
[3, 5, 6, 2, 1, 54, 97]
[2, 1, 3, 6, 5, 54, 97]
[1, 2, 3, 6, 5, 54, 97]
[1, 2, 3, 6, 5, 54, 97]
[1, 2, 3, 6, 5, 54, 97]
[1, 2, 3, 6, 5, 54, 97]
[1, 2, 3, 5, 6, 54, 97]
[1, 2, 3, 5, 6, 54, 97]
[1, 2, 3, 5, 6, 54, 97]
[1, 2, 3, 5, 6, 54, 97]
[1, 2, 3, 5, 6, 54, 97]
[1, 2, 3, 5, 6, 54, 97]
sorted List =  [1, 2, 3, 5, 6, 54, 97]
memory loc 3: 2340241016704

image.png

Shell sort¶

v1.gif

In [2]:
def shell(list1):
    gap=len(list1)//2
    
    while gap > 0:
        
        for index in range(gap,len(list1)):
            current=list1[index]
        
            position = index
        
            while position >= gap and current < list1[position-gap]:
                list1[position] =list1[position-gap]
                position=position-gap

            list1[position] = current
        gap=gap//2
    
li=[54,5,6,2,1,97,3]
shell(li) 
print(li)
[1, 2, 3, 5, 6, 54, 97]
In [ ]: